package com.lw.leetcode.binary.b;

/**
 * 540. 有序数组中的单一元素
 * 剑指 Offer II 070. 排序数组中只出现一次的数字
 *
 * @Author liw
 * @Date 2021/5/23 12:35
 * @Version 1.0
 */
public class SingleNonDuplicate {

    public static void main(String[] args) {
        SingleNonDuplicate test = new SingleNonDuplicate();
        int[] arr = {1, 1, 2, 2, 3, 4, 4, 8, 8};
        int i = test.singleNonDuplicate(arr);
        System.out.println(i);
    }

    public int singleNonDuplicate(int[] nums) {
        int length = nums.length;
        if (length == 1 || nums[0] != nums[1]) {
            return nums[0];
        }
        if (nums[length - 1] != nums[length - 2]) {
            return nums[length - 1];
        }
        int st = 1;
        int end = length - 2;

        while (st < end) {
            int m = st + ((end - st) >> 1);
            if ((m & 1) == 0) {
                if (nums[m] == nums[m + 1]) {
                    st = m + 2;
                } else {
                    end = m;
                }
            } else {
                if (nums[m] == nums[m - 1]) {
                    st = m + 1;
                } else {
                    end = m;
                }
            }
        }
        return nums[st];
    }
}
